引入

我们知道如何构建一个图的数据结构，那么现在，我们看看如何根据一棵图的图形，创建一张图到内存中去。

创建数据结构

1
2
3
4
5
6
7
8

#define MAX_VEX_NUM 50  //最大的容量暂定为50
typedef enum {DG, UDG} GraphType;  //选择有向图还是无向图
typedef struct {
    char vexs[MAX_VEX_NUM];  //一维数组存储顶点
    int arcs[MAX_VEX_NUM][MAX_VEX_NUM];   //二维数组（邻接矩阵）存储边
    int vexnum, arcnum;  //记录顶点的数量和边的数量，等下用作循环判断条件
    GraphType type;  //记录图得类型
} MGraph;

数据结构中

• 记录顶点的数量和边的数量，等下用作循环判断条件
• 记录图得类型，等下用于写入矩阵

引入

学了那么多图的知识，是时候动手设计一下图的存储结构了，图跟线性表、树有那么大得差别，所以图的数据结构要复杂很多。

思考

我们先回忆一下线性表和树得存储结构

• 线性表：一对一的关系，用数组和链表就能很好的表示。
• 树：一对多得关系，用数组和链表得特性结合在一起就可以很好的表示。

那么图呢？

• 图上的任意一个顶点都可以是第一个顶点，谁开始都行。
• 任意一个顶点的邻接点也不存在次序关系，多对多，大家都一样。

我们观察下面的四张图

引入

前面我们基本讲了什么是图结构，以及顶点、边和弧之间不同状态的特殊图结构，我们今天继续，看看这些顶点、边和弧之间的关系。

关系

我们来讲讲顶点和边的一些关系

顶点和边的关系

我们说，如果存在一个无向图，G（V，E）

• 图中的两个顶点构成的边$(V1 , V2)\in E$属于 E 的集合
• 那么我们就说 V1 和 V2 互为邻接点（Adjacent）
• 也就说明 V1 和 V2 相邻接，不是连接！。
• 对于边(V1 , V2)来说
• 边(V1 , V2)依附（Incident）于 顶点 V1和 V2
• 也可以说边(V1 , V2)与顶点 V1 、V2 相关联

无向图中的度

引入

终于，我们迎来了新的数据结构，图结构。之前的线性表，主要是一对一的关系，一个元素和另一个元素的关系。树结构，主要层与层之间一对多的关系，即一个结点可以有 N 个子树，N 个子树也只对应一个双亲结点。那么大家也应该猜到了，图解决的是多对多的数据关系。

图的定义

（顶点1有一个环的图结构）

图（Graph）：是有顶点的又穷非空集合和顶点之间的边集合组成。

• 通常表示为G（V，E）
• G 是一个图
• V 是图 G 中顶点的集合
• E 是图 G 中边的集合。

未完待续…

未完待续…

引入

上一节我们发现，树、森林和二叉树之间竟然有这么多有趣的关联，前根和后根遍历结果竟然都可以跟二叉树相同。二叉树竟然这么的独特，今天我们就来看看，如何打造一棵完美二叉树！

从一个问题出发

我们在使用二叉树的时候，会遇到类似这样的问题

• 这是一棵二叉树，结点连接线上的数字，是访问这个结点的概率
• 我们有5%的几率访问 A、15%访问 B、70%访问 C、10%访问 D
• 那么问题来了，既然绝大多数都是访问 C 的
• 那访问 C 必须要先判断是否是 A 或者 B，这样太麻烦了

要弄清楚这个问题，我先首先要弄清楚刚才哪些加了数字的结点是什么。

引入

我们学习了树、二叉树、以及森林的知识。我们直到遍历二叉树非常的方便，甚至学会了给二叉树增加线索，提高效率。那么问题来了，如果一棵树，不是二叉树，一个结点下有 N 个孩子，那么我们遍历和操作起来，就会很复杂，因为不知道这棵树是深度长还是宽度广，如果都能转换成二叉树来操作就爽了！今天我们就看看普通树和森林，如何转换成二叉树。

普通树转换为二叉树

既然二叉树最方便操作，我们如何能够将普通树转换成二叉树呢？

上面是一棵普通树，有三层，我们将这棵树转换成二叉树

60秒读全文

这是一篇在 Nintendo Switch 6.2.0系统上，将游戏数据和存档从 128G 内存卡 转移 到 256G 内存卡，转移成功后，下载的游戏数据及存档有被 Switch 系统认到，并可正常使用的。

引入

前天下了《任天堂明星大乱斗 特别版》的时候，发现自己去年11月买的 128G microSD 卡竟然满了，以为能用一段时间呢… 今天进入 Manage Software 一看《DOOM》竟然要 30G ，《异度之刃2》、《任天堂明星大乱斗 特别版》、《Diabol III》都要十几个 G ，所以入了 256 G 的新 microSD 卡，老卡就留着之后进军 Vlog 吧。
至于为什么要写这篇文章呢？因为发现网上流传的几种方法我复现都失败了，也算是记录一下，万一下次换 512G 的内存卡呢？废话不多说，老 128G microSD 卡换256G，游戏文件和存档该如何转移呢？我们接着看~

准备

我们在开始前，请确认下面的东西已经准备好了

• Nintendo Switch 主机一台。
• 老内存卡：我的就是128G 的老卡，不要动里面的数据。
• 新内存卡：不用提前格式化，等下会讲。
• 高速读卡器：如果没有像我 110+G 要等死…
• PC / Mac：用于操作文件转移。

引入

上一节，我们试着解决了树在存储时空间浪费和没法找到双亲结点的问题，这一节，我们着重看一下如何用代码实现。这篇难度有一点大，请务必沉住气，认真仔细。

思路拆解

我们一步一步的拆解代码来看看。

创建树结构体

我们首先声明我们重新设计的线索二叉树结点

• char data 存放结点数据
• 左孩子、右孩子这个不用细说了吧，
• Ltag 和 Rtag 主要是判断左孩子和右孩子究竟是指向左右孩子还是前驱后继
• 我们定义结构体的时候，使用了 typedef
• 后面所有的 BiTNode 你可以理解为 struct BiTNode，代表该结构体
• 后面所有的 BiTree 你可以理解为 struct BiTNode *，代表结构体指针
• 注意上面有个星号哈！

1
2
3
4
5
6
7
8
9
10
11
12

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct BiTNode)

typedef enum{link,thread} NodeState;
typedef struct BiTNode{
    char data;
    struct BiTNode *Lchild;
    struct BiTNode *Rchild;
    NodeState Ltag;
    NodeState Rtag;
}BiTNode,*BiTree;